﻿//189. 轮转数组
//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。


//解法一：翻转数组
class Solution {
public:
    void reserve(vector<int>& nums, int begin, int end)
    {
        while (begin < end)
            swap(nums[begin++], nums[end--]);
    }
    void rotate(vector<int>& nums, int k)
    {
        k = k % nums.size() - 1;
        reserve(nums, 0, nums.size() - 1);
        reserve(nums, 0, k);
        reserve(nums, k + 1, nums.size() - 1);
    }
};

//解法二：
class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        k %= nums.size();
        for (int i = 0, cnt = 0; cnt < nums.size(); i++)
        {
            int j = i, tmp = nums[i];
            do
            {
                int sp = (j + k) % nums.size();
                swap(tmp, nums[sp]);
                j = sp;
                sp = (sp + k) % nums.size();
                cnt++;
            } while (j != i);
        }
    }
};